import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mirac
 * Date: 2025-09-08
 * Time: 23:31
 */
public class Solution {
    public static void main(String[] args) {
        String[] s = {"i","love","leetcode","i","love","coding"};
        String[] s1 = {"love","i","coding"};
        String[] s2 = {"i","love","coding"};
        Solution solution = new Solution();
        List<String> list = solution.topKFrequent(s,3);
        for (String str:
                list) {
            System.out.print(str + " ");
        }
    }
    public List<String> topKFrequent(String[] words, int k) {
        HashMap<String,Integer> map = new HashMap<>();
        //统计每个单词出现的次数
        for (String word:
             words) {
            if (map.get(word) == null) {
                map.put(word,1);
            }else {
                map.put(word,map.get(word) + 1);
            }
        }

        //建立小根堆
        PriorityQueue<Map.Entry<String,Integer>> minHeap =
                new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
                    @Override
                    public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                        if (o1.getValue().compareTo(o2.getValue()) == 0) {
                            return o2.getKey().compareTo(o1.getKey());
                        }
                        return o1.getValue().compareTo(o2.getValue());
                    }
                });

        //遍历map
        for (Map.Entry<String,Integer> entry:
             map.entrySet()) {
            if (minHeap.size() < k) {
                minHeap.offer(entry);
            }else {
                Map.Entry<String,Integer> top = minHeap.peek();
                if (top.getValue().compareTo(entry.getValue()) < 0) {
                    minHeap.poll();
                    minHeap.offer(entry);
                }else if (top.getValue().compareTo(entry.getValue()) == 0){
                    if (top.getKey().compareTo(entry.getKey()) > 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }
        //直接打印会按照出现的频率由低到高打印，因此这里需要逆序
        ArrayList<String> list = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry<String,Integer> tmp = minHeap.poll();
            list.add(tmp.getKey());
        }
        //Collections 用于对集合进行操作
        Collections.reverse(list);
        return list;
    }

}
